#include "All_Sort.h"
#include "Swap.h"
#include <time.h>
#include <stdlib.h>

//冒泡排序，时O(n^2)，空O(1)，稳定
//比较次数n(n-1)/2，交换次数：初始数组逆序数
//依次与下一个比较交换，每次排序可以确定一个元素的最终位置
void BubbleSort(int *arr, int startIdx, int endIdx)
{
    for (int i = startIdx; i < endIdx; ++i)
    {
        for (int j = i + 1; j <= endIdx; ++j)
        {
            if(arr[i] > arr[j])
            {
                Swap(&arr[i], &arr[j]);
            }
        }
    }
}

//选择排序，时O(n^2)，空O(1)，不稳定
//比较次数n(n-1)/2，交换次数：0 ~ (n-1)
//每次排序可以确定一个元素的最终位置
void SelectSort(int *arr, int startIdx, int endIdx)
{
    int minIdx;
    for (int i = startIdx; i < endIdx; ++i)
    {
        minIdx = i;
        for (int j = i + 1; j <= endIdx; ++j)
        {
            if(arr[minIdx] > arr[j])
            {
                minIdx = j;
            }
        }
        Swap(&arr[minIdx], &arr[i]);
    }
}

//插入排序，时O(n^2)，空O(1)，稳定
//比较次数n-1 ~ n(n-1)/2，交换次数：0 ~ n(n-1)/2
//适用于初始序列大量有序的情况
void InsertSort(int *arr, int startIdx, int endIdx)
{
    for (int i = startIdx; i <= endIdx; ++i)
    {
        for (int j = i; j > startIdx && arr[j - 1] > arr[j]; --j)
        {
            Swap(&arr[j], &arr[j - 1]);
        }
    }
}

//希尔排序，时O(n^2)，空O(1)，不稳定
//比较次数：O(n^1.3)，交换次数：O(n^1.3)
//基于插入排序的改良
void ShellSort(int *arr, int startIdx, int endIdx)
{
    int i, j, gap = startIdx + (endIdx - startIdx) / 2;//防溢出
    for(gap; gap > 0; gap /= 2)
    {
        for (i = startIdx + gap; i <= endIdx; ++i)
        {
            for (j = i; j >= startIdx + gap && arr[j - gap] > arr[j]; j -= gap)
            {
                Swap(&arr[j], &arr[j - gap]);
            }
        }
    }
}

#pragma region  归并排序
void Merge(int *arr, int left, int mid, int right)
{
    int helpArr[right - left + 1];
    int i = 0, pL = left, pR = mid + 1;
    while (pL <= mid && pR <= right) //取小者
    {
        helpArr[i++] = arr[pL] <= arr[pR] ? arr[pL++] : arr[pR++];
    }
    while (pL <= mid)
    {
        helpArr[i++] = arr[pL++];
    }
    while (pR <= right)
    {
        helpArr[i++] = arr[pR++];
    }
    for (int j = 0; j < i; ++j)//拷贝数组至原数组
    {
        arr[left + j] = helpArr[j];
    }
}

//归并排序，时O(n*logn)，空O(n)，稳定
//比较次数：，交换次数：
//用了排外序方法，可用master公式求得时间复杂度
void MergeSort(int *arr, int startIdx, int endIdx)
{
    if(startIdx == endIdx)
    {
        return;
    }
    int mid = startIdx + (endIdx - startIdx) / 2;
    MergeSort(arr, startIdx, mid);
    MergeSort(arr, mid + 1, endIdx);
    Merge(arr, startIdx, mid, endIdx);
}
#pragma endregion

//快速排序，时O(n*logn)，空O(logn)，不稳定
void QuickSort(int *arr, int startIdx, int endIdx)
{
    if(startIdx < endIdx)
    {
        srand(time(0));
        int randVal = arr[startIdx + rand() % (endIdx - startIdx + 1)];//取数组的随机元素作为划分值
        int lessIdx = startIdx - 1, moreIdx = endIdx + 1;
        int i = startIdx;
        while (i < moreIdx)
        {
            if(arr[i] < randVal)
            {
                Swap(&arr[++lessIdx], &arr[i++]);
            }   
            else if(arr[i] > randVal)
            {
                Swap(&arr[--moreIdx], &arr[i]);
            }
            else
            {
                i++;
            }
        }
        QuickSort(arr, startIdx, lessIdx);
        QuickSort(arr, moreIdx, endIdx);
    }
}

#pragma region  堆排序

//将处于index上的元素在堆中向上调整
void HeapInsert(int* heapArr, int index)
{
    int parentIdx = (index - 1) / 2; // index = 0时，该值也为0
    while(heapArr[index] > heapArr[parentIdx])
    {
        Swap(&heapArr[index], &heapArr[parentIdx]);
        index = parentIdx;
    }
}

//将处在index上的元素在堆中向下调整
void Heapify(int* heapArr, int index, int heapSize)
{
    int left = index * 2 + 1;
    while (left < heapSize)
    {
        int better = left + 1 < heapSize && heapArr[left + 1] > heapArr[left] ? left + 1 : left;
        if(heapArr[index] >= heapArr[better])
            break;
        Swap(&heapArr[better], &heapArr[index]);
        index = better;
        left = index * 2 + 1;
    }
}

//堆排序，时O(n*logn)，空O(1)，不稳定
void HeapSort(int* arr, int startIdx, int endIdx)
{
    if(startIdx >= endIdx) 
        return;
    int heapSize = endIdx - startIdx + 1;
    //装入堆数组
    int heapArr[heapSize];
    for (int i = 0; i < heapSize; ++i)
    {
        heapArr[i] = arr[startIdx + i];
    }
    //大根堆化，只需从中间开始即可
    for (int i = heapSize / 2; i >= 0; --i)
    {
        Heapify(heapArr, i, heapSize);
    }
    //排序
    while(heapSize > 0)
    {
        Swap(&heapArr[0], &heapArr[--heapSize]);
        Heapify(heapArr, 0, heapSize);
    }
    //传回原始数组
    for (int i = startIdx, j = 0; i <= endIdx; ++i, ++j)
    {
        arr[i] = heapArr[j];
    }
}

#pragma endregion

#pragma region 基数排序

//获取数组中最长的位数
int GetMaxDigitCount(int *arr, int startIdx, int endIdx)
{
    int max = INT_MIN;
    for (int i = startIdx; i <= endIdx; ++i)
    {
        if(arr[i] > max)
        {
            max = arr[i];
        }
    }
    int res = 0;
    while (max != 0)
    {
        ++res;
        max /= 10;
    }
    return res;
}

//获取指定十进制位上的数
int GetDigitNum(int num, int digit)
{
    int tp = 1;
    for (int i = 1; i < digit; ++i)
    {
        tp *= 10;
    }
    return num / tp % 10;
}

//基数排序，时O(n*k)，空O(n)，稳定，非基于比较
void RadixSort(int *arr, int startIdx, int endIdx)
{
    int help[endIdx - startIdx + 1];
    int i, j;
    int maxDigitCount = GetMaxDigitCount(arr, startIdx, endIdx);
    for (int curDigit = 1; curDigit <= maxDigitCount; ++curDigit)
    {
        int bucket[10] = {0};//记录各位的数的桶
        for (j = startIdx; j <= endIdx; ++j)//数频统计
        {
            ++bucket[GetDigitNum(arr[j], curDigit)];
        }
        for (j = 1; j < 10; ++j)//数频累加和
        {
            bucket[j] += bucket[j - 1];
        }
        for (j = endIdx; j >= startIdx; --j)//出桶
        {
            help[--bucket[GetDigitNum(arr[j], curDigit)]] = arr[j];
        }
        for (i = 0, j = startIdx; j <= endIdx; ++i, ++j)//用新数组排序
        {
            arr[j] = help[i];
        }
    }
}

#pragma endregion